package com.singzi.leetcode.N100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class T0040 {
    public static void main(String[] args) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int key:map.keySet()){

        }
        List<Integer> list = new ArrayList<>();
        list.add(1);
        Integer []nums = list.toArray(new Integer[0]);

    }
}
class Solution0040 {
    List<List<Integer>> list;
    boolean flag;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        list = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        backTrace(candidates, temp, target, 0, 0);
        flag = false;
        return list;

    }

    private void backTrace(int[] candidates, List<Integer> temp, int target, int index, int sum) {
        if(sum == target){
            list.add(new ArrayList<>(temp));
            return;
        }
        for(int i = index;i < candidates.length;i++){
            if(i > 0 && candidates[i]==candidates[i-1] && !flag) continue;
            if(sum > target) break;
            temp.add(candidates[i]);
            backTrace(candidates, temp, target, i+1, sum+candidates[i]);
            temp.remove(temp.size() - 1);
            flag = true;
        }

    }
}